package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/02/02 09:03
 **/

/**
 * 题目 ：按摩师
 * 题目详述 ：
 * 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
 * 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 *
 */
public class Massage {
    /**
     * 思路 ：
     * ===> 即，类似于动态规划的单序列问题;（求解最优的预约集合）
     *
     * 假设f(i)为长度为i的请求序列的最长总预约时间;
     * ===》
     * 状态转移方程 ：
     * （1）第i-1个请求不被处理的话 ：
     *  f(i) = f(i-1);
     * （1）第i-1个请求被处理的话 ：
     *  f(i) = f(i-2);
     *  ===》 f(i) = max(f(i-1) , f(i-2) + nums[i]);
     * @param nums
     * @return
     */
    public int massage(int[] nums) {
        int len = nums.length;
        int[] dp = new int[2];
        if(len == 0){
            return 0;
        }
        dp[0] = nums[0];
        if(len > 1){
            dp[1] = Math.max(nums[0] , nums[1]);
        }
        for(int i = 2 ; i < len ; i++){
            dp[i % 2] = Math.max(dp[(i - 1) % 2] , dp[(i - 2) % 2] + nums[i]);
        }
        return dp[(len - 1) % 2];
    }
}
